#!/usr/bin/python3

"""
@group: actually_is_dolan
@author: Lauge Groes, Florian Biermann {lgro, fbie}@itu.dk
"""

class Edge:
    def __init__(self, l, r, length):
        self.l = l
        self.r = r
        self.length = length

class Node:    
    def __init__(self, name):
        self.root = self
        self.name = name
        self.edges = []
        self.visited = False
        self.rank = 0

def find(node):
    if node.root == node:
        return node
    node.root = find(node.root) 
    return node.root

def union(a, b):
    a_root = find(a)
    b_root = find(b)
    
    if a_root == b_root:
        return False
    
    if a_root.rank < b_root.rank:
        a_root.root = b_root
    elif a_root.rank > b_root.rank:
        b_root.root = a_root
    else:
        a_root.root = b_root
        b_root.rank += 1
        
    return a_root.root
    
def walk_recursively(node):
    if not node.visited:
        node.visited = True
        for edge in node.edges:
            walk_recursively(edge.l)
            walk_recursively(edge.r)

def spanning_usa(nodes, edges):
    edges.sort(key=(lambda x: x.length))
    root = None
    chosen_edges = []
    
    while len(edges) > 0:
        edge = edges.pop(0)
        
        if not edge.l.root == edge.r.root:
            new_root = union(edge.l, edge.r)
            if new_root:
                edge.l.edges.append(edge)
                edge.r.edges.append(edge)
                chosen_edges.append(edge)
                root = new_root

    walk_recursively(root)
    for node in nodes.values():
        assert node.visited, "%s not visited!" %node.name
    
    return sum(edge.length for edge in chosen_edges)

def parse(filename):
    import re
    p_edge = re.compile('(.+)--(.+)\s\[(\d+)\]')
    
    nodes = {}
    edges = []
    
    with open(filename, "r") as graph:
        for line in graph:
            if not "--" in line:
                name = line.rstrip()
                nodes[name] = Node(name)
            else:
                match = re.search(p_edge, line)
                node_l = nodes[match.group(1)]
                node_r = nodes[match.group(2)]
                
                length = int(match.group(3))
                edges.append(Edge(node_l, node_r, length))
            
    return nodes, edges

if __name__ == "__main__":
    import sys
    
    for arg in sys.argv[1:]:
        nodes, edges = parse(arg)
        size = spanning_usa(nodes, edges)
        print(size)
        if arg.endswith("USA-highway-miles.in"):
            assert size == 16598